Міністерство освіти і науки, молоді та спорту України
Вінницький національний технічний університет
Інститут Інформаційних Технологій та Комп’ютерної Інженерії
Лабараторна робота № 4
з дисципліни: Дискретна математика.
Тема: Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом ядерних рядків.
м.Вінниця 2013 Мета роботи: набути навиків застосування методу ядерних рядків для побудови покриття на множинах.
Порядок виконання роботи:
Ознайомитися з методом ядерних рядків..
Отримати варіант індивідуального завдання для виконання.
Розробити схему алгоритму побудови покриття методом ядерних рядків.
Розробити програму побудови покриття методом ядерних рядків.
Для заданого варіанту принести результати тестування програми у покроковому режимі.
Зробити висновки про результати застосування цього методу для побудови покриття
Завдання №25
Блок – схема програми що реалізує метод ядерних рядків для побудови покриття на множинах.
Результати виконання програми.
/
Рисунок 2.
Висновок: В ході виконання лабораторної роботи було розроблено блок-схему, та програму, яка розв’язує методу ядерних рядків для побудови покриття на множинах, у ході роботи було представлено результати тестування програми яку розроблено на мові С++.
Додаток(лістинг програми, що реалізує метод ядерних рядків для побудови покриття на множинах)
#include <stdio.h>
#include <iostream>
#include <stdafx.h>
int main()
{
int i, j, k,m, sum[10]={0}, rt, se, sum1[10]={0}, max=-1, mas[10]={0,1,2,3,4,5,6,7,8,9}, s, t=10;
int znak[10]={10}, b=0, post;
int core[10], io=0, zor=0, tos=0, sot=0, pogl[10]={11,11,11,11,11,11,11,11,11,11},p, sum2[10]={0};
char arr[10]={'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
int a[10][10] = { {1,0,1,0,0,0,1,1,0,0},{0,1,1,0,1,0,0,0,0,1},{0,0,1,1,1,0,0,1,0,0},{1,1,0,0,0,1,1,0,0,0},
{1,0,0,0,0,1,0,0,0,1}, {0,0,0,0,1,1,1,0,1,1},{1,1,1,0,0,0,0,1,0,0}, {0,0,1,0,1,0,1,1,0,1}, {1,0,0,0,0,1,0,0,0,1},
{0,1,0,0,0,0,1,0,0,0}};
puts ("Vvedit kilkist strok:");
scanf ("%d", &k);
puts ("Vvedit kilkist stovpciv:");
scanf ("%d", &m);
for(i=0;i<k;i++)
{
printf ("%c = ", arr[i]);
for(j=0;j<m;j++)
{
cout << a[i][j]<<" ";
}
cout<<endl;
}
for (rt=0; rt<10; rt++)
{
sum[rt]=0;
}
for(i=0;i<m;i++) // Пошук ядерних стовпчиків
{
for (se=0; se<t; se++)
{
if (i==mas[se])
{
for(j=0;j<k;j++)
{
sum[i]=sum[i]+a[j][i];
}
if (sum[i]==1) { core[io]=i; io++; }
};
}
}
for (rt=0; rt<10; rt++)
{
sum1[rt]=0;
}
for (i=0; i<k; i++) // Пошук ядерних рядків
{
for (int lost=0; lost<io; lost++)
{
if (a[i][core[lost]]==1)
{
znak[zor]=i;
zor++;
}
}
}
s=0;
for (i=0; i<m; i++)
{
for (se=0; se<t; se++)
{
if (i==mas[se])
{
if (a[znak[0]][i]+a[znak[1]][i]==0)
{
mas[s]=i;
s++;
}
}
}
}
for (rt=s; rt<10; rt++)
{
mas[rt]=11;
}
p=0;
for (i=0; i<s; i++)
{
tos=0;
for (j=0; j<k; j++)
{
if (i+1<s)
{
if (a[j][mas[i]]>=a[j][mas[i+1]])
{
tos++;
}
if (a[j][mas[i]]<=a[j][mas[i+1]])
{
sot++;
}
}
}
if (tos==k) {
mas[i]=11;
}
if (sot==k) { mas[i]=11;
}
}
int qwe=0, r=0;
for (i=0; i<10; i++)
{
if (mas[i]!=11) qwe++;
}
for (i=0;i<k;i++)
{
for (j=0; j<qwe; j++)
{
for (r=0; r<k; r++)
{
if (j==mas[r])
{
sum2[i]=sum2[i]+a[i][mas[j]];
}
}
}
if (sum2[i]>max) max=sum2[i];
}
int roz;
roz=zor;
for (i=0; i<k; i++) // остання перевірка
{
if (sum2[i]==max)
{znak[roz]=i;
roz++;}
}
for (i=0; i<zor-1; i++)
{
if (znak[i]>znak[i+1])
{
post=znak[i];
znak[i]=znak[i+1];
znak[i+1]=post;
}
}
int rozzor=roz-zor;
printf ("\nPokruttya:\n");
for (j=0; j<(rozzor); j++)
{
printf ("%c", arr[znak[i]]);
}
printf ("%c", arr[znak[zor+j]]);
printf ("\n"); }
